IEEE 1588 PTP is defined in the IEEE 1588-2002 (Version 1) and 1588-2008 (Version 2) standards. IEEE 1588 is designed as an improvement to current methods of synchronization within a distributed network of devices. It is designed for systems requiring very high accuracies beyond those attainable using Network Time Protocol (NTP). The IEEE 1588, unlike NTP, is able to deliver timing accuracy well under a microsecond. It is also designed for applications that cannot bear the cost of a GPS receiver at each node, or for which the GPS signals are inaccessible as is the case with a majority of picocell and femtocell base stations.
IEEE 1588 is now the industry accepted packet-based protocol used for transferring timing information to clocks of distributed systems to allow them to be synchronized to a master with accuracies in the nanoseconds level. PTP is a message based protocol that can be implemented across a range of packet based networking technologies, not limited to Ethernet. The underlying principle is a master/slave concept based on regular exchange of synchronization messages. IEEE 1588 synchronizes all slave clocks by allowing to them adjust their frequency/time to highest quality clock (the GrandMaster clock).
Packet delay variation (“PDV”) is the main factor affecting the accuracy and stability of slave clocks when using packet timing protocols such as IEEE 1588 PTP. The PDV is introduced by packet network devices such as switches and routers that receive and queue packets between a sender and receiver. PDV is a direct contributor to the noise in the recovered clock. Unless mitigated, the higher the PDV, the higher the clock noise and subsequently the poorer the clock quality. If the clock noise exceeds application defined thresholds the clocks are unusable for the end system. The term clock noise here refers to all impairments to the timing information recovered at the slave including jitter, wander and other imperfections in the recovered clocks.
For instance, for time synchronization, the delay variations experienced by packets traversing the packet network translate into noise in the slave's perception of the time at the master. Variable delay causes a varying estimate of the time offset between slave and master clocks. For these reasons, synchronization mechanisms used for end-to-end timing transfer require PDV mitigation mechanisms in order to accurately reconstruct the master clock. The performance of the slave's clock recovery process is highly affected by how efficient the packet selection algorithm (i.e., PDV mitigation mechanism) used by the slave is at reducing the level of PDV seen by the slave.
Overview of IEEE 1588v2 PTP
The GrandMaster (GM) is the timing reference in a domain and transmits synchronization information to the clocks residing in its domain. In IEEE 1588v2 PTP messages are categorized into event and general messages. All IEEE 1588 PTP messages have a common header. Event messages are timed messages with generated accurate timestamp at both transmission and receipt of each message. Event messages have to be accurately timestamped since the accuracy in transmission and receipt timestamps directly affects clock distribution accuracy. A timestamp event is generated at the time of transmission and reception of any event message. The set of event messages consists of Sync, DelayReq, Pdelay_Req and Pdelay_Resp. The set of general messages consists of Announce, Follow_Up, Delay_Resp, Pdelay_Resp_Follow_Up, Management and Signaling.
IEEE 1588 PTP allows for two different types of timestamping methods, either one-step or two step. One-step clocks update time information within event messages (Sync and Delay_Req) on-the-fly, while two-step clocks convey the precise timestamps of packets in general messages (Follow_Up and Delay_Resp).
The Sync, Delay_Req, Follow_Up and Delay_Resp messages are used to generate and communicate the timing information needed to synchronize ordinary and boundary clocks using the delay request-response mechanism. A Sync message is transmitted by a master to its slaves and either contains the exact time of its transmission or is followed by a Follow_Up message containing this time. In a two step ordinary or boundary clock, the Follow_Up message communicates the value of the departure timestamp for a particular Sync message. A Delay_Req message is a request for the receiving node to return the time at which the Delay_Req message was received, using a Delay_Resp message.
A basic pattern of synchronization message exchanges for the one step and two-step clocks are illustrated in FIG. 1 and FIG. 2, respectively. The message exchange pattern for the one-step clock can be explained as follows. The master 1 sends a Sync message to the slave 3 over the network 2 and includes the exact transmission time T1 timestamp in the Sync message as it departs. The timestamp should be generated by the hardware as close as possible to the physical layer (network media) in order to minimize the error introduced by the delay between the application layer and physical layer. The slave 3 receives the Sync message and notes the time of the reception T2. Next, the slave 3 sends a Delay_Req message to the master 1 and notes the time at which it was sent T3. The master 1 receives the Delay_Req message and notes the time of reception T4. The master conveys to the slave 3 the timestamp T4 by embedding it in a Delay_Resp message.
At the end of this PTP message exchange, the slave 3 possesses all four timestamps {T1, T2, T3, T4}. These timestamps may be used to compute the offset of the slave's clock 5 with respect to the master clock 4 and the mean propagation time of messages between the two clocks. The computation of offset and propagation time assumes that the master-to-slave and slave-to-master propagation times are equal, i.e. a symmetrical communication path.
Like NTP, PTP requires an accurate measurement of the communication path delay between the time server (master) 1 and the client (slave) 3. PTP measures the exact message transmit and receive times and uses these times to calculate the communication path delay and clock offset. This delay measurement principle determines the path delay between devices on the network and the local clocks 4 are adjusted for this delay using the series of messages sent between master 1 and slaves 3 (as shown in FIG. 1 and FIG. 2).
In addition to the fixed propagation (or physical communication medium) delay, any packet traveling through the packet network 2 might experience additional variable delays as it travels from sender to receiver due to traffic loading and scheduling in the network components (switches, routers). That is, instead of the constant travel time (caused by the physical distance) the packets show variable delay according to the network topology and current load. FIG. 3 and FIG. 4 illustrate this with the original messages 21 being transmitted at a constant interval, but the message stream 22 arriving at the receiver having variable inter-message gaps due to the PDV.
A packet selection mechanism can be used in this end-to-end timing transfer scenario to reduce the effects of PDV on the recovered clock at the slave.
Packet Pre-Processing (Selection) for Clock Recovery
One way of delivering frequency/time from a master 1 to a slave 3 is to send IEEE 1588 PTP messages in an end-to-end manner as illustrated in FIG. 5 (i.e. without any assistance from the intermediate network devices 6). In this case the slave 3 is solely responsible for correctly recovering the master clock signal in the presence of all the PDV generated by the network 2. Compared to the other frequency/time transfer methods (e.g., using hop-by-hop Boundary Clocks or Transparent Clocks), clock recovery here is more challenging because the slave 3 is exposed to all the PDV generated by the intermediate packet network 2.
The recovered clock from the PTP timing signal at the slave 3 contains clock noise (contributed largely by PDV) that needs to be removed. A filtering process is typically used at the slave 3 to filter out the clock noise, thus generating a “smooth” clock output. This process is also often referred to as clock recovery. The clock recovery process in packet networks often involves two major components, a packet pre-processing module 10 and a phase-locked loop (PLL) or servo control mechanism 20 as illustrated in FIG. 6.                Packet Pre-Processing: This module 10 in FIG. 6 represents the application of specialized algorithms that are used to mitigate the impact of network-induced PDV. The goal of the packet selection block is to select from all the input packets to the slave clock a certain subset that are the least affected by the packet switched network. These packets would thus best reflect the timing signal at the transmitter.        Phase-Locked Loop: This module 20 represents a servo control function that disciplines the local clock to bring its output (frequency or time) into alignment with the master's. The servo control function is generally present in all clock recovery mechanisms.        
These two mechanisms are used together to attenuate the clock noise introduced by the packet network to levels commensurate with the clock output requirements of the application. Both the packet selection block 10 and the low pass filter function of the PLL 20 work to remove noise from the packet timing signal to faithfully re-create the timing source. The ‘cleaned’ timing signal can then be used to discipline the local oscillator.
The two modules in FIG. 6 are outside of the scope of the IEEE 1588 standard. The packet pre-processing algorithms 10 and PLL mechanisms 20 are vendor implementation specific and often proprietary. These two mechanisms and the quality of the PLL oscillator 23 represent the two most important factors that determine the performance of a clock. The PLL 20 introduces a low-pass filter characteristic in the path between the master and the slave clock output, and a high-pass filter characteristic between the local oscillator and the clock output (PLL output).
The PLL 20 has low-pass and high-pass characteristics with a common corner frequency. The bandwidth of the loop comprises the frequencies below the corner frequency. The following observations can be made about the filtering characteristics of the PLL:                All components of the PDV after packet pre-processing entering the loop and above the corner frequency will be filtered out (attenuated) significantly. All components of the PDV after packet pre-processing below the corner frequency (mostly wander, defined as noise or jitter below 10 Hz) will be passed through to the clock output.        All components of the local PLL oscillator 23 clock noise below the corner frequency will be filtered out. All components of the local oscillator noise above the corner frequency will be passed through to the clock output.        
The filtering behavior of the PLL 20 is equivalent to an “averaging” process where the time-constant represents the duration over which the averaging is performed. The PLL cut-off frequency and time-constant have a reciprocal relationship and are equivalent descriptors of the low-pass filtering action.
From the above discussion we see that in the absence of packet pre-processing, the low-pass filtering action of the PLL 20 is solely responsible for attenuating the entire PDV so that the recovered clock will be compliant with the clock requirements of the application. To achieve this, the low-pass filter of the PLL may have to be designed to have a very small cutoff frequency (meaning PLL has very small bandwidth). The drawback, however, in doing this is that the very low-pass PLL leads to a high-pass characteristic where the loop allows more local oscillator noise to pass through to the clock output. This means that the reduction of the bandwidth of the PLL should not be done arbitrarily, but should take into account the quality of the local oscillator. It is for these reasons that applications with more stringent requirements demand higher quality oscillators. A high quality oscillator is stable and generates less noise that passes through to the clock output. At this point, it should be appreciated that packet pre-processing significantly helps to reduce the clock noise power at the PLL input and thereby can be used to alleviate the requirement of a very high quality (and expensive) oscillator. Efficient pre-processing can allow for the use of less expensive oscillators.
In the general case without packet pre-processing, synchronization performance is affected to a great extent by network design and its characteristics: traffic loading, PDV, route changes, etc. The greater the PDV, the more difficult it is to maintain synchronization between master and slave. Even with packet pre-processing (selection), the quality of the recovered clock at the slave will depend on how well the packet selection algorithm screens out the PDV in the arriving PTP messages.
Basics of Packet Selection for Clock Recovery
The basic schema of the packet selection process is illustrated in FIG. 7. The idea of packet selection for clock recovery is as follows. In the packet network 2 there is a constant stream of timing related packets 22 (see FIG. 3). Each timing packet arrives experiencing a different delay generated according to the actual load along its path. A packet selection is performed within a certain window or “sampling interval” 11 (a set of previously arrived packets of length L). A packet selection function 12 then tries to repeatedly select the “best” or optimal packet 13 within the window which has the lowest delay variance (PDV), and present this to the clock recovery mechanism with the goal that it minimizes the overall clock noise introduced by the PDV.
The most important piece or block in FIG. 7 is how well the “packet selection function” 12 is implemented as this block performs the operation of selecting the most appropriate packet from the set of the last packets in the selection window 11. The following section discusses some example packet selection functions.
Commonly Used Packet Selection Techniques
As explained above, in order to reduce the clock noise produced as a result of the PDV, the slave 3 implements a packet selection (pre-processing) technique that allows it to use only a subset of the received timing packets, that is, the timing packets that are least affected by PDV. The idea is to select a specific subset of the PDV affected samples, having similar delay properties, among the entire population of PDV samples and pass these to the slave clock recovery mechanism.
Let {xk} denote samples of a hypothetical packet time-error signal x(t). In packet timing scenarios the time error signal is typically based on measurements of the transit delay of (timing) packets over the network between the master 1 and slave 3. Let xn represent the delay of the nth timing packet through the network and letXk={xn}, kL≦n≦(k+1)L−1,  (1)be a vector representing the kth window of size L on which the packet selection operation is performed. Typically, in PTP the packet transit delay xn (the elements of vector Xk) of Sync messages are calculated by taking the difference between the departure timestamp T1(n) and the arrival timestamp T2(n):xn=T2(n)−T1(n).  (2)
Similarly, the transit delays of Delay_Req messages can be calculated using T4(n) and T3(n) as shown in FIG. 1 and FIG. 2. For the kth window, the packet selector obtains a single value from Xk by using a function that operates on this vector,yk=g(Xk)  (3)
Some examples of the simplest packet selection methods are described below. Other more advanced methods such as percentile, band and cluster are described in the literature (e.g., [1][2][[3][4]).                Sample Minimum Packet Selection Method (“Min”):        
This method involves selecting the minimum delay within a window of delay samples. This selection function can be represented as follows:g(Xk)=min{xk}, kL≦n≦(k+1)L−1  (4)
The minimum packet selection and percentile packet selection both focus on packet data at the floor. The notion of “floor delay” is equivalent to the notion of minimum possible transit delay of packets over a network.                Sample Maximum Packet Selection Method (“Max”):        
This method involves selecting the maximum delay within a window of delay samples. This selection function can be represented as follows:g(Xk)=max{xn}, kL≦n≦(k+1)L−1  (5)                Sample Mean Packet Selection Method (“Mean”):        
This method involves selecting the mean delay of delay samples within a window. This selection function can be represented as follows:
                              g          ⁡                      (                          X              k                        )                          =                              1            L                    ⁢                                    ∑                              n                =                kL                                                                                  (                                          k                      +                      1                                        )                                    ⁢                  L                                -                1                                      ⁢                          x              n                                                          (        6        )            
In the above packet selection methods, the representative delay value obtained in a window (min, max, or mean value) are used in some form in the packet recovery mechanism at the slave.
Timing Precision Evaluation in Packet Networks
In order for a slave to optimally recover time and frequency, packet selection is essential. The performance of a packet selection (pre-processing) method can be assessed by applying a stability quantification metric over the selected group of samples. This is illustrated schematically in FIG. 8. This assessment is done in order to get an estimation of the achievable output clock quality. Such a metric could serve as a useful tool for comparing different packet pre-processing methods.
As illustrated in FIG. 8, with packet pre-processing, a packet selection algorithm 12 is applied to the packet delay sequence, and the standard metrics such as TDEV (Time Deviation), MATIE (Maximum Average Time Interval Error), or MAFE (Maximum Average Frequency Error) calculation 14 is applied on the modified packet delay sequence. If Xk is the original packet delay sequence, and X′k is the modified packet delay sequence, the idea is that TDEV, MATIE, or MAFE operates on the X′k sequence rather than original Xk sequence. In this way, calculations with packet selection provide insight into how a slave clock recovery algorithm might perform under the studied network conditions.
As indicated above, a number of packet selection algorithms can be applied to Xk. These time windows can be either overlapping or non-overlapping. In the minimum packet selection method (“min”), effective for sequences with a good population of minimum delay packets, the minimum in the window is selected. The percentile method takes a number of packets at or near the minimum, and averages them together to produce an X′k sequence sample. The band selection method first sorts all the data in a time window from minimum to maximum, then selects a cluster of points at some chosen range, say between the 20th and 30th percentiles, and averages them together to produce a sample in the X′k sequence.
We explain briefly here why TDEV has become an important stability qualification metric for timing studies. This has become a common metric that is used to analyze the performance of a packet-based synchronization mechanism such as IEEE 1588 PTP. Variances are commonly used to characterize the fluctuation of a frequency source, but standard variance is not suitable for frequency stability measurement [2, 3]. The Allan Variance/Deviation, Modified Alan Variance/Deviation (MVAR/MDEV) and Time Deviation (TDEV) are the most common metrics used to quantify frequency stability. Specifically, TDEV is related to the MDEV and is used globally in the telecommunications industry to measure the time stability of frequency sources. However, it has been noted in the ITU-T standard [4] there can be some discrepancies between the information provided by a given PDV metrics and the real performance achieved by a slave clock. The regular TDEV metrics is defined as follows:
                              σ          ⁡                      (            τ            )                          =                              TDEV            ⁡                          (              τ              )                                =                                                    1                                  6                  ⁢                                      n                    2                                                              ⁢                              〈                                                      [                                                                  ∑                                                  i                          =                          1                                                n                                            ⁢                                              (                                                                              x                                                          i                              +                                                              2                                ⁢                                n                                                                                                              -                                                      2                            ⁢                                                          x                                                              i                                +                                n                                                                                                              +                                                      x                            i                                                                          )                                                              ]                                    2                                〉                                                                        (        7        )            where τ=n·τ0τ=n·τ0, τ0 is a packet arrival frequency, n is length of a selection window, {•} is an ensemble average. In the use of the regular TDEV with packet pre-processed, the packet selection is done prior to the stability calculation, where the TDEV is applied to the resulting sequence (which is performed in the traditional way). This is how we compare the performance of all the proposed techniques set out.
Note the above approach for computing TDEV using packet pre-processing is different from the integrated packet selection approach, where the packet selection is integrated into the metric calculation [2][4]. Generally integrated packet selection approach involves replacing a full population averaging calculation with a selection process that may or may not itself include averaging. Integrated packet selection replaces the averaging with a selection process such as the min, percentile, and band. As a result a new self-contained metric is formed such as minTDEV, percentileTDEV, bandTDEV, minMAFE, percentileMAFE, or bandMAFE. An example of this is to replace the averaging operation present within the TDEV calculation with a minimum selection process forming a new calculation, i.e. minTDEV(x) [2][4].
Review of Some Packet Selection Studies
So far, there has not been extensive research done in the area of packet selection mechanisms for the clock recovery beyond the basics described in the ITU-T standards (min, percentile, band, cluster). The most relevant research in this area was carried out by Hadić and Morgan [1]. They proposed an adaptive technique based on very simple criteria (minimum, maximum and mean) for the packet selection. These simple criteria were derived from studies carried out by measuring and analyzing the PDV characteristics of different network topologies and traffic loading.
In order to analyze the performance of the techniques proposed in the present invention the PDV distributions obtained in [1] will be used, which are deemed realistic enough for synchronization studies. The PDV distribution in [1] has been accurately modelled to obtain the histograms in FIG. 9. Details of the network topologies, traffic loading, PDV characterization and models, and packet selection discussions are given in [1].
Based on the measured PDV distributions three different types of packet selection techniques were derived in [1]. We will refer to the PDV distributions for the 20%, 40% and 80% load scenarios as the minPDV, maxPDV and meanPDV distributions, respectively. The studies in [1] determined that for the 20%, 40% and 80% network load scenarios, the minimum, maximum and mean packet selection criteria were optimal, respectively. We therefore call this technique here the Min/Max/Mean Algorithm (MMMA).
The idea behind the selection of these particular criteria in [1] is simple. By applying the criteria on the different distribution in FIG. 9 and analyzing their effects, it was observed that these criteria resulted in the selection of timing packets that produced the least variance as shown in FIG. 10. Paper [1] observes that for the leftmost (rightmost) figures, there are a rich number of samples (packets) arriving with minimum (maximum) values and as a result there is no variance if the minimum (maximum) values are selected; for the middle figure, the least variance is obtained if the mean value of the selection window is selected.
From the above discussion we can see that the MMMA is directly tied to the PDV distribution (FIG. 10). Specifically, it constrains the types of PDV distributions to three. As a packet selection algorithm plays an important role in the mitigation of PDV and given the wide possible range of network topologies and traffic loading, we see that relying on the assumption of the existence of only three different PDV distributions is unrealistic.
An object of the present invention is to provide a packet selection technique that significantly reduces the PDV when the selected packets are compared to the complete set of packets received by a device.
An further object of the present invention is to provide a packet selection technique that works well regardless of the network topology, traffic loading, and PDV distribution. In particular it is desirable that any technique should work well regardless of the type of PDV distribution it is exposed to (for example, whether left-skewed, centered or right-skewed as shown in FIG. 9).
It is a further object of the present invention to provide a packet selection technique which can be used in a clock synchronization technique to improve the overall quality of the synchronized clock in the slave device, more particularly by reducing the clock variation introduced by PDV.